#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <memory>
#include <cmath>
#include <bitset>
#include <queue>
#include <vector>
#include <stack>
using namespace std;

#define CLR(x, y) memset(x, y, sizeof(x))
#define MIN(m, v) (m) < (v) ? (m) : (v)
#define MAX(m, v) (m) > (v) ? (m) : (v)
#define ABS(x) ((x) > 0 ? (x) : -(x))
#define rep(i, x, y) for (i = x; i < y; ++i)

const int MAXN = 1100000;

int t, n, m, d;
int s[MAXN];
int dp[MAXN][2];

void Solve()
{
	char c;

	scanf("%d", &t);
	while (t--)
	{
		scanf("%d%d%d", &n, &m, &d);
		getchar();
		CLR(s, 0);
		for (int i = m - 1; i >= 0; --i)
		{
			scanf("%c", &c);
			s[i] = c - '0';
		}
		if (s[0] == 0)
		{
			dp[0][0] = 1;
			dp[0][1] = 0;
		}
		else
		{
			dp[0][0] = 1;
			dp[0][1] = 1;
		}
		for (int i = 1; i < n; ++i)
		{
			if (s[i] == 1)
			{
				dp[i][0] = dp[i - 1][0];
				dp[i][1] = dp[i - 1][0] + dp[i - 1][1];
			}
			else
			{
				dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
				dp[i][1] = dp[i - 1][1];
			}
			if (dp[i][0] >= d)
				dp[i][0] -= d;
			if (dp[i][1] >= d)
				dp[i][1] -= d;
		}
		cout << (dp[n - 1][0]) << endl;
	}
}

int main()
{
	Solve();
	return 0;
}